package com.suanfa;

import javax.swing.tree.TreeNode;
import java.util.Enumeration;
import java.util.Queue;
import java.util.LinkedList;

public class Tree
{
    /*
     * 输入一棵二叉树，求该树的深度。
     * 从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
     * */
    public int TreeDepth(TreeNode root)
    {
        //1、递归
//         if(root ==null) return 0;
//         int leftdepth=TreeDepth(root.left);
//         int rightdepth=TreeDepth(root.right);
//         int deep=1+(leftdepth>rightdepth?leftdepth:rightdepth);
//         return deep;

        //2、层次遍历
        if (root == null) return 0;
        TreeNode current;//记录当前节点
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        int index, width;   //index记录访问到当前层的第几个，width是当前层的宽度
        int deep = 0;
        queue.offer(root);
        while (!queue.isEmpty())  //队列不空，循环记录深度
        {
            index = 0;// 新的一层index为0
            width = queue.size();//当前队列里的节点即为该层的所有节点
            while (index < width)//循环访问该层的所有节点
            {
                current = queue.poll();//即将出队的头
                if (current.getChildAt(1) != null)//左节点不空，左节点入队列
                {
                    queue.offer(current.getChildAt(1));
                }
                if (current.getChildAt(2) != null)//右节点不空，右节点入队列
                {
                    queue.offer(current.getChildAt(2));
                }
//                if(current.right!=null)//右节点不空，右节点入队列
//                {
//                    queue.offer(current.right);
//                }
                index++; //访问完当前节点后index++
            }
            deep++;//访问完一层，层数++
        }
        return deep;
    }
}
